1. Field of the Invention
The present invention relates to scheduling algorithms for packet transmission and, more particularly, to a method and apparatus for packet scheduling in a wireless network.
2. Description of the Background Art
In several types of wireless networks, such as wireless local area networks (WLANs) and cellular telephone networks, packets destined for individual mobile stations accumulate in a buffer until they can be served by a base station and transmitted to their destinations. A flow of data traffic (i.e., a sequence of packets) can be identified for each mobile station served by the base station. In such wireless networks, the base station may utilize different data transmission rates among the mobile stations, depending on channel quality. An important area of current study is how to best devise a scheduling algorithm that directs the base station, at a given time, how to allocate its total capacity among individual data transmission rates to the respective mobile stations.
Current probabilistic packet-based scheduling algorithms, such as the modified largest weighted delay first (M-LWDF) algorithm, have been shown to achieve suboptimal performance when scheduling heterogeneous traffic flows under conditions of continued network instability. Additional problems exist for such algorithms during periods of transmission rate oscillation. For example, the M-LWDF algorithm relies on the ratio of instantaneous transmission rate to average transmission rate for each of the mobile stations to assign priorities to respective traffic flows. However, when such a ratio is employed, the following occurs:
1) A traffic flow will immediately receive high priority after the transmit rate spikes upwards, but will then receive lower and lower priority as the transmit rate stabilizes.
2) As the transmit rate decreases the flow is given lower priority, resulting in increased queuing delay. This will force the packet to be transmitted when the flow is near its lowest recent transmit rate.
3) After the flow reaches its minimum transmit rate and maintains such minimum transmit rate for a period of time, the average is minimized. If the transmit rate begins to climb, the ratio of instantaneous transmission rate to average transmission rate will quickly increase again, causing the system to transmit at or near the lowest transmit rate.4) If the transmit rate is quickly cycling between two extremes, the result is a high priority for the traffic flow after a large upswing, and a low priority for the traffic flow after a large downswing. This is somewhat arbitrary. As the cycling is occurring quickly, there is benefit (in terms of overall system capacity) in waiting until the transmit rate stabilizes before adjusting the priority for the traffic flow.5) If the channel is unstable, the ratio of instantaneous transmission rate to average transmission rate yields alternating high and low priority to the flow. The priority may become unsynchronized with the transmit rate.
Accordingly, there exists a need in the art for a method and apparatus for packet scheduling that exhibits improved performance in conditions of network instability and transmission rate oscillation.